/*

*/

#include "SimpleFS.h"

// Function: init_return_user()
// Purpose:  This gets called if our FS was detected in the user's current dir. The func grabs important
//           values from disk to set global variables, etc.
int init_return_user()
{
	char fname[] = "init_return_user()";
	Inode * inode = new Inode();
	unsigned int offset;

	// Make sure fs I/O obj still has file open (sometimes its closed after returning from func)
	if(! fs.is_open() ) { 
		fs.open(FS_NAME);  // leave this open until the end of main
		if(fs.fail()) {
			cout << "\nError: Our file system cannot be opened for use in " << fname << "!\n" << endl;
			if(WINDOWS_DEV) system("pause"); // let user read error before closing window
			return -1;
		}
	}
	// ROOT INODE
	// read in the offset of the root inode
	fs.type_read(ROOT_INODE_PTR_POSITION, &offset, fname);
	cwd.push(offset);  // store the offset to the root inode

	// FREE HEAD: grab val from disk and assign to global var "free_head"
	fs.type_read(FREE_HEAD_PTR_POSITION, &free_head, fname);
	if(free_head == 0)
		free_list_empty = true;
	else
		free_list_empty = false;

} ////// end init_return_user() //////////


int mkfs_handle_errors_keep_file_open(string func_name)
{
	int retval;
	/*
	cout << "\nWelcome earthling.  Our file system was not detected in your current "
			  << "directory.\nBefore you may execute any commands, the file system must be "
				<< "created.\nTherefore, \"mkfs\" is being executed for you now...\n";
	*/
	cout << "\nOur file system is now being created (in your current dir) and formatted for use ..." << endl;

	// Create & format the new fs
	retval = fs_mkfs();  // func also opens the fs I/O object
	// if error in mkfs()
	if(retval < 0 ) {
		if(WINDOWS_DEV) system("pause"); // let user read error from prev function before closing window
		return -1;
	}
	// Make sure the FS I/O obj file is still open at this point
	retval = verify_fs_open(func_name);
	if( retval < 0 ) return retval;
	
	cout << "\n...File system creation and formatting now complete." << endl << endl;

	return 0;
} //// end mkfs_handle_errors_keep_file_open() ////


// Makes sure fs I/O obj still has file open (sometimes its closed after returning from diff func)
int verify_fs_open(string fname)
{
	if(! fs.is_open() ) { 
		fs.open(FS_NAME);  // leave this open until the end of main
		if(fs.fail()) {
			cout << "\nError: Our file system cannot be opened for use in " << fname << "!\n" << endl;
			if(WINDOWS_DEV) system("pause"); // let user read error before closing window
			return -1;
		}
	}
	return 0;
} //// end verify_fs_open() ////



/*
Creates a file system or formats an existing one.
*/
int fs_mkfs()
{
	char* fname = "fs_mkfs()";
	const int buffsize = 256;
	int retval;
	char buf[buffsize] = {0};
	FList_node f;
	const int buff2_size = 256;
	char buf2[buff2_size] = "";
	char* func_name = "fs_mkfs()";
	//char temp[12];

	/////////////////////////////////////////////////////////////////////////////////////////////
	//// HANDLE RETURNING/CURRENT USER CALLING MKFS (Remove their old fs and start over) ////////

	if(fs.is_open()) { // close the open file used for our fs for a current user
		fs.close();
	}
	// Attempt to open our fs (for users who have already created it)
	// This open attempt will fail if the file does not yet exist (i.e., new user) (fstream class fails)
	fs.open(FS_NAME);
	// NEW USER (fs NOT found in their current dir)
	if(fs.fail()) { 
	         // (do nothing; rest of this func will create the new file system)
		fs.clear();  // must reset the fail bit or later checks for fail() will return true
	}
	// RETURNING USER (fs found in their current dir)
	else {

		////////////////////////////////////////////
		//// DELETE OLD FILE ///////////////////////
				
		cout << "\nDeleting your old file system now..." << endl;

		fs.close();   // must close the file before we can delete it
		if(fs.fail()) {	cerr <<"\nfs.close() failed\n"<<endl; if(WINDOWS_DEV) system("pause"); exit(-1);	}
		// delete old fs file
		bool fSuccess = DeleteFile(TEXT(FS_NAME));
    if (!fSuccess) { printf ("DeleteFile failed (%d)\n", GetLastError()); if(WINDOWS_DEV) system("pause"); exit(-12);  }
		///////////////////////////////////////////
		//// CLEAR OUT MEMORY DATA STRUCTURES /////
		cwd_name.clear();
		while(cwd.size() > 0) //pop off all entries 
			cwd.pop();		  
		
		oft.clear(); // clear out the open file table

		//////////////////////////////////////////
		//// RUN MKFS() AGAIN TO START OVER //////
		
		// run mkfs from scratch
		retval = mkfs_handle_errors_keep_file_open(fname);
		if(retval < 0 ) return retval;
		else            return 0;
	} // end dealing with a return/current user calling mkfs() ///////
	
	////////////////////////////////////////////////////////////////////////
	///// CREATE AND FORMAT NEW FILE SYSTEM ////////////////////////////////

	// Open new file for our fs, in output mode only (must use ofstream for this part)
	ofstream file(FS_NAME);

	if(file.fail()) {
		cout << "\nMain File system file creation failed in "<<func_name<<"!\n" << endl;
		return -1;
	}

	// Fill the entire "disk" with data to set its size
	for(int i = 0; i < (FS_SIZE / buffsize); i++) {
		file.write(buf,buffsize);
		if(file.bad()) {
			cout << "\nFile system file WRITE failed in "<<func_name<<"!\n" << endl;
			return -1;
		}
	}
	file.flush();
	file.close(); // closing it since this obj is for output only (reopened below in better obj)

	// Now that fs has been created & formatted, open it as fstream type for I/O by other cmds
	fs.open(FS_NAME);  // leave this open until the end of main
	if(fs.fail()) {
		cout << "\nError: Our file system was created, but it now cannot be opened for use!\n" << endl;
		return -1;
	}
	/////////////////////////////////////////////
	//// Setup FREE LIST stuff //////////////////
	free_head = DS_PTRS_SIZE;  // initially the one free-list nd starts after data structure ptrs @ beg of fs
	f.size = FS_SIZE - DS_PTRS_SIZE;  // initially the whole fs is free space except the main DS pointers
	f.flink = 0;  // equivalent to NULL for our purposes
	f.blink = 0;

	vector<unsigned int> vec;  // to hold several unsigned ints (so I can write several to disk at once)
	vec.push_back(free_head);  vec.push_back(f.size); vec.push_back(f.flink);  vec.push_back(f.blink);

	// write the 4 ints to disk
	fs.type_write(FREE_HEAD_PTR_POSITION, vec, func_name);
	if(test_mkfs) { cout << "\nIn mkfs, just wrote to disk: free_head_ptr and starting free node."
	                     << "\nNext I'll make the root inode..." << endl;
	}
	/////////////////////////////////////////////////
	//// setup ROOT INODE stuff /////////////////////
	unsigned int root_offset = carve( sizeof(Inode) ); // get disk memory for it
	// write the ptr to the root inode to disk
	fs.type_write(ROOT_INODE_PTR_POSITION, root_offset, func_name );
	// put on vec for testing carve()'s correctness
	//test_offsets.push_back(root_offset);
	test_offsets.insert(root_offset);
	if(test_mkfs) cout << "\ncarve() gave me offset <" << root_offset << "> for an inode of size <" 
		                 << sizeof(Inode) << ">" << endl;

	// Fill in inode 
	Inode* inode = new Inode;
	strcpy(inode->name, "/"); // "/" is root dir name
	inode->dir  = true;
	inode->children = 0;
	inode->data = 0;
	inode->eof  = 0;
	inode->eof_block_pos = 0;
	inode->next = 0;
	inode->prev = 0;
	inode->modified = time(NULL);
	inode->parent = 0;
	inode->size = sizeof(Inode);
	inode->location = root_offset;
	inode->link_count = 1;
	inode->num_blocks = 0;
	inode->link_next  = 0;
	inode->link_prev  = 0;
	// write the actual root inode to disk
	fs.fwrite(root_offset, (char*)inode, sizeof(Inode), func_name );
	if(test_mkfs) cout << "\nIn mkfs, just wrote to disk: root inode." << endl;
	//clear the cwd stack
	//cwd.empty();
	//push root inode location to cwd stack
	cwd.push(root_offset);
	

	return 0;
} /// end fs_mkfs() ///

/*
This function opens an existing file or creates a new
one, assigns a file descriptor to it, and returns that 
descriptor.  Upon failure, -1 is returned.

If a file is opened with read-only permissions, the r/w pointer is
positioned at the beginning of the file.

If a file is opened with read/write or write-only permissions the 
r/w pointer is positioned at the end of the file.
*/
int fs_open(const char * filename, int flag)
{
	//Ready, go!!

	map<int, Oft_entry>::iterator it;  // key is file descriptor
	pair<map<int, Oft_entry>::iterator,bool> ret;
	Inode * file = get_inode(filename);
	
	//check if file is already open (traverse entire oft searching for it)
	for(it = oft.begin(); it != oft.end(); it++)
	{
		if(strcmp(filename, it->second.inode->name) == 0 && flag == it->second.flag 
			&& it->second.inode->location == file->location)
		{
			return it->first;
		}
		else if(strcmp(filename, it->second.inode->name) == 0 
			&& it->second.inode->location == file->location)
		{
			cout << "File is already open.  Changing flag..." << endl;
			it->second.flag = flag;

			if(flag == FS_O_RDONLY)
			{
				it->second.d_offset = it->second.inode->data + FILE_SEG_INFO_SIZE;
				it->second.block_pos = FILE_SEG_INFO_SIZE;
			}
			else
			{
				it->second.d_offset = it->second.inode->eof;
				it->second.block_pos = it->second.inode->eof_block_pos;
			}
			
			return it->first;
		}
	}
	
	//find the first unused key value
	int i;
	for(i = 1; ;i++)
		if(oft.find(i) == oft.end()) // if this key is not in the OFT map
			break;
	
	
	Oft_entry * t = new Oft_entry();
	
	if(file == 0 && flag == FS_O_RDONLY)
	{
		cout << "Non-existant file cannot be opened read-only." << endl;
		return -1;
	}
	else if(file == 0)  // File doesn't exist yet, so...
	{
		//create a new file and get its inode
		create_file(filename, BLOCK_SZ - FILE_SEG_INFO_SIZE);  
		file = get_inode(filename);
		//out of disk space
		if(file == 0)
			return -1;

		//build the Oft_entry
		t->inode = file;
		t->d_offset = file->eof;
		t->block_pos = FILE_SEG_INFO_SIZE;
		//t->f_offset = 0;
		t->flag = flag;
	}
	else if(flag == FS_O_RDONLY)
	{
		//build the Oft_entry
		t->inode = file;
		t->d_offset = file->data + FILE_SEG_INFO_SIZE; // for R_ONLY, position read/write ptr at beg of file
		t->block_pos = FILE_SEG_INFO_SIZE;
		t->flag = flag;
	}
	else  // File already exists, so just load its inode in OFT, etc
	{
		//build the Oft_entry
		t->inode = file;
		t->d_offset = file->eof;
		//t->f_offset = 0; //This may change once write is implemented.
		t->block_pos = file->eof_block_pos;
		t->flag = flag;
	}
	
	//insert the file into the oft
	ret = oft.insert(pair<int, Oft_entry>(i,*t));
	
	//return the file descriptor
	return ret.first->first;
} /////////// end fs_open() /////////////////

/*
This function closes an open file by freeing up the file
descriptor assigned to it.  Upon success, it returns 0.
Upon failure, it returns -1.

This function also has the task of deleting an open file
which has zero links to its data

i.e. An open file cannot be deleted while it is open, but
when it is closed, it must then be deleted.
*/
int fs_close(int fd)
{
	char * fname = "fs_close()";
	Inode inode;

	if(oft.find(fd) == oft.end())
	{
		cout << "File descriptor does not refer to an open file." << endl;
		return -1;
	}
	else
	{
		//write out the updated inode?  No, since this inode might not have the up-to-date
		// link count, and each write() updates all linked files' metadata.
				//fs.fwrite(oft[fd].inode->location, (char*)oft[fd].inode, sizeof(Inode), fname);
		 
		////////////////////////////////////////
		///// HANDLE UNLINKING if necessary ////

		// Copy the inode (deep copy) out of the oft before removing it
		inode = *(oft[fd].inode);
		oft.erase(fd); // must remove it from oft before calling unlink

		// If unlink had been called on this file while it is open, its link count could now be
		//  less than 1... so we would need to call unlink on it now.
		if(inode.link_count < 1 ) {
			// Temporarily push this inode's parent onto cwd so unlink can refer to the relative 
			//  path that is stored in the inode's name field.
			cwd.push(inode.parent);
			fs_unlink(inode.name);  // delete the file.
			cwd.pop(); // remove the temporary cwd
		}

	}
	return 0;
} /////// end fs_close() ///////////

/*
Reads a certain number of bytes, given a file descriptor, and prints them to the console.
On success, returns the number of bytes read.
On failure, returns -1.
*/
int fs_read (int fd, char * buf, int count)
{
	char * fname = "fs_read()";
	unsigned int bytes_read = 0;

	if(count == 0)
		return count;
	else if(oft.find(fd) == oft.end())
	{
		cout << "No file associated with that descriptor." << endl;
		return -1;
	}
	else if(oft[fd].flag == FS_O_WRONLY)
	{
		cout << "File is write-only.  To read from it re-open it with the proper permissions." << endl;
		return -1;
	}
	else
	{
		unsigned int offset = oft[fd].d_offset;
		Inode * inode = oft[fd].inode;
		unsigned int left = BLOCK_SZ  - oft[fd].block_pos;
		unsigned int current = inode->data;  // first block of data
		

		for(int i = 0; i < count && offset != inode->eof; i++)
		{
			fs.fread(offset, buf + i, 1, fname);
			if(buf[i] == '\r')
				buf[i] = '\n';
			offset++;
			bytes_read++;
			left--;

			if(left == 0)
			{
				fs.type_read(current + BLOCK_NEXT_PTR_POS, &current, fname);
				offset = current + FILE_SEG_INFO_SIZE;
				left = BLOCK_SZ - FILE_SEG_INFO_SIZE;
			}
		}

		oft[fd].d_offset = offset;
		oft[fd].block_pos = BLOCK_SZ - left;
	}
	
	return bytes_read;
}

/*
Prints the contents of a file.
On success, returns 0.
On failure, returns -1.
*/
int  fs_cat(const char * filename)
{
	char * fname = "fs_cat()";

	//Attempt get the inode of the specified file from the cwd
	Inode * inode = get_inode(filename);

	if(inode == 0 || inode->dir == true)
	{
		cout << "No such file."  << endl;
		return -1;
	}
	else
	{
		unsigned int offset = inode->data +	FILE_SEG_INFO_SIZE;
		unsigned int left = BLOCK_SZ  - FILE_SEG_INFO_SIZE;
		unsigned int current = inode->data;  // first block of data
		char buffer;
		string contents;
		

		for(int i = 0; offset != inode->eof; i++)
		{
			fs.fread(offset, &buffer, 1, fname);
			if(buffer != '\r')
				contents += buffer;
			else
				contents += '\n';
			offset++;
			left--;

			if(left == 0)
			{
				fs.type_read(current + BLOCK_NEXT_PTR_POS, &current, fname);
				offset = current + FILE_SEG_INFO_SIZE;
				left = BLOCK_SZ - FILE_SEG_INFO_SIZE;
			}
		}

		cout << contents << endl;

		return 0;
	}
}

/*
Writes bytes to a file, given a file descriptor.
On success, returns the number of bytes written.
On failure, returns -1.
*/
int fs_write (int fd, const char * buf, int count)
{
	char * fname = "fs_write()";
	char newline = '\n';
	
	if(oft.find(fd) == oft.end())
	{
		cout << "No file associated with that descriptor." << endl;
		return -1;
	}
	else if(oft[fd].flag == FS_O_RDONLY)
	{
		cout << "File is read-only.  To write to it re-open it with the proper permissions." << endl;
		return -1;
	}
	else
	{
		unsigned int offset = oft[fd].d_offset;  
		Inode * inode = oft[fd].inode;  // makes a more readable inode ptr
		unsigned int left = BLOCK_SZ - oft[fd].block_pos;
		unsigned int current = oft[fd].d_offset - oft[fd].block_pos;  // first block of data
		unsigned int next;                   // for next data block
		unsigned int new_blocks = 0;
		bool past_eof = false;
		
		// Get copy of inode from disk to make sure we have most up-to-date copy 
		//   (in case links have been added, etc)
		fs.fread(inode->location, (char*)inode, sizeof(Inode), fname);


		fs.type_read(current + BLOCK_NEXT_PTR_POS, &next, fname);
		
		
		for(int i = 0; i < count; i++)
		{
			if(buf[i] == '\\' && buf[i+1] == 'n')
			{
				fs.fwrite(offset, &newline, 1, fname);
				i++;
			}
			else
			{
				fs.fwrite(offset, buf + i, 1, fname);
			}
			
			offset++;
			left--;

			if(left == 0)
			{
				if(next == 0)//Just in case we're not eof here, lol
				{
					new_blocks++;
					next = carve(BLOCK_SZ);
					if(next == 0) 
					{
						cout << "Out of disk space" << endl;
						return -1;
					}

					//write the next and previous ptr's
					fs.type_write(current + BLOCK_NEXT_PTR_POS, next, fname);
					fs.type_write(next + BLOCK_PREV_PTR_POS, current, fname);
					fs.type_write(next + BLOCK_NEXT_PTR_POS, 0, fname);
				}

				current = next;
				fs.type_read(current + BLOCK_NEXT_PTR_POS, &next, fname);
				offset = current + FILE_SEG_INFO_SIZE;
				left = BLOCK_SZ - FILE_SEG_INFO_SIZE;
			}
		}

		//change the last modified time
		inode->modified = time(0);
		inode->size += new_blocks * BLOCK_SZ;
		inode->num_blocks += new_blocks;
		if(new_blocks > 0 || (inode->num_blocks == 1 && offset > inode->eof))
		{
			inode->eof = offset;
			inode->eof_block_pos = BLOCK_SZ - left;
		}
		oft[fd].d_offset = offset;
		oft[fd].block_pos = BLOCK_SZ - left;
		//write out the updated inode (in case user forgets to close(), etc)
		fs.fwrite(oft[fd].inode->location, (char*)oft[fd].inode, sizeof(Inode), fname);
		// Update all linked files
		update_all_links(oft[fd].inode);
	} // end the "else" block of normal writes

	
	return count;
} //////////// fs_write() //////////////////

/*
This function repositions the r/w pointer associated with a file descriptor.
If the user attempts to read past the eof, the pointer is positioned at the eof.
On success, the position in the file of the r/w pointer is returned.
On failure, returns -1;
*/
int fs_seek (int fd, int offset)
{
	//Whoo!
	char * fname = "fs_seek()";
	unsigned int file_offset = 0;

	if(oft.find(fd) == oft.end())
	{
		cout << "No file associated with that descriptor." << endl;
		return -1;
	}
	else if(offset < 0)
	{
		cout << "Offset must be positive." << endl;
		return -1;
	}
	else
	{
		//Start at the beginning of the first block and move 
		//forward to the desired offset
		Inode * inode = oft[fd].inode;
		unsigned int cur_pos = inode->data + FILE_SEG_INFO_SIZE;
		unsigned int left = BLOCK_SZ - FILE_SEG_INFO_SIZE;
		unsigned int current = inode->data;  // first block of data
		

		for(int i = 0; i < offset && cur_pos != inode->eof; i++)
		{
			cur_pos++;
			file_offset++;
			left--;

			if(left == 0)
			{
				fs.type_read(current + BLOCK_NEXT_PTR_POS, &current, fname);
				cur_pos = current + FILE_SEG_INFO_SIZE;
				left = BLOCK_SZ - FILE_SEG_INFO_SIZE;
			}
		}

		if(cur_pos == inode->eof)
		{
			cout << "End of file reached." << endl;
		}

		oft[fd].d_offset = cur_pos;
		oft[fd].block_pos = BLOCK_SZ - left;
	}
	
	return file_offset;
}

/*
This function creates an empty directy inside the cwd.
If there is already a file or directory by that name,
it will fail.
On success, returns 0.
On failure, returns -1.
*/
int fs_mkdir (const char * dirname)
{
	//Here we go!!
	char * fname = "fs_mkdir";
	unsigned int offset;
	Inode * n = new Inode(); //new Inode
	Inode * t = new Inode(); //temporary Inode
	
	//Populate the inode ("prev" and "location" get set below)
	strcpy(n->name, dirname);
	n->children = 0;
	n->data = 0;
	n->eof  = 0;
	n->eof_block_pos = 0;
	n->dir = true;
	n->modified = time(NULL);
	n->next = 0;
	n->parent = cwd.top();
	n->size = sizeof(Inode);
	n->link_count = 1;
	n->num_blocks = 0;
	n->link_next  = 0;
	n->link_prev  = 0;
	//read the current directory inode from disk
	Inode * p = new Inode();
	fs.fread(cwd.top(), (char*) p, sizeof(Inode), fname);
	
	//allocate space for the new inode
	offset = carve(sizeof(Inode));
	if(offset == 0)
	{
		cout << "Out of disk space." << endl;
		return -1;
	}
	n->location = offset;
	//////////////////////////////////////////////////////////////////////
	// INSERT THE NEW CHILD DIR AS A CHILD (and potentially a sibling) ///
	//       (deal with parent/child/sibling pointers)                 ///

	//if the parent directory has no children, start the child list
	if(p->children == 0)
	{
		p->children = offset;

		n->prev = 0;
		
		//write the new and modified inodes to disk
		fs.fwrite(p->location, (char*)p, sizeof(Inode), fname);
		fs.fwrite(offset, (char*)n, sizeof(Inode), fname);

	}
	else //iterate to the end of the list and add the new directory on
	{
		
		//read in the first child from disk
		fs.fread(p->children, (char*)t, sizeof(Inode), fname);
		
		if(strcmp(t->name,dirname) == 0)
		{
			cout << "Directory by that name already exists." << endl;
			return -1;
		}

		while(t->next != 0)
		{
			fs.fread(t->next, (char*)t, sizeof(Inode), fname);
			
			if(strcmp(t->name,dirname) == 0)
			{
				cout << "Directory by that name already exists." << endl;
				return -1;
			}
		}

		t->next = offset;
		n->prev = t->location;

		//write the new and modified inodes to disk
		fs.fwrite(t->location, (char*)t, sizeof(Inode), fname);
		fs.fwrite(offset, (char*)n, sizeof(Inode), fname);
	}
	
	return 0;
} ////// end mkdir() /////////////

/*
Removes a directory from the current working directory.
On success, returns 0.
On failure, returns -1.
*/
int fs_rmdir (const char * dirname)
{
	//Let's go!!  (go getup tiger)
	char * fname = "fs_fmdir()";
	Inode * d = get_inode(dirname); //get the inode of the directory if it exists
	Inode * temp1 = new Inode();
	Inode * temp2 = new Inode();

	if(d == 0)
	{
		cout << "No such directory." << endl;
		return -1;
	}
	else if(d->children != 0)
	{
		cout << "Directory is not empty." << endl;
		return -1;
	}
	else
	{
		//Multiple cases for child list
		
		//if directory is the only child
		if(d->prev == 0 && d->next == 0)
		{	
			//read cwd inode
			fs.fread(cwd.top(), (char*)temp1, sizeof(Inode), fname);

			temp1->children = 0;
			//write it back out
			fs.fwrite(cwd.top(), (char*)temp1, sizeof(Inode), fname);
		}
		//if directory is at the beginning of the list
		else if(d->prev == 0)
		{

			//read in the cwd inode and the next inode in the list
			//then change the variables up, and finally, write them back out
			fs.fread(cwd.top(), (char*)temp1, sizeof(Inode), fname);
			fs.fread(d->next, (char*)temp2, sizeof(Inode), fname);
			temp1->children = temp2->location;
			temp2->prev = 0;
			fs.fwrite(cwd.top(), (char*)temp1, sizeof(Inode), fname);
			fs.fwrite(d->next, (char*)temp2, sizeof(Inode), fname);

		}
		//if directory is at the end of the list
		else if(d->next == 0)
		{

			//read in the adjacent inode in the list, modify it, and  write it out
			fs.fread(d->prev, (char*)temp1, sizeof(Inode), fname);
			temp1->next = 0;
			fs.fwrite(d->prev, (char*)temp1, sizeof(Inode), fname);

		}
		//if directory is somewhere in the middle of the list
		else
		{
			//read in the adjacent inodes in the list, point them to each other,
			//and write them back out
			fs.fread(d->prev, (char*)temp1, sizeof(Inode), fname);
			fs.fread(d->next, (char*)temp2, sizeof(Inode), fname);
			temp1->next = temp2->location;
			temp2->prev = temp1->location;
			fs.fwrite(d->prev, (char*)temp1, sizeof(Inode), fname);
			fs.fwrite(d->next, (char*)temp2, sizeof(Inode), fname);
		}

		//finally, free the space
		my_free(d->location);

	}
	return 0;
}

/*
This function changes the current working directory.
On success, returns 0.
On failure, returns -1.
*/
int fs_chdir (const char * dirname)
{
	
	char fname[] = "fs_chdir()";
	
	string path(dirname); //Set up a string to hold the path
	stack<unsigned int> backup(cwd); //save the current directory
	deque<string> name_backup(cwd_name);
	Inode * t = new Inode();
		
	if(path[0] == '/') //check for absolute path
	{
		while(cwd.size() > 1) //pop entries off the cwd stack until we're left
			cwd.pop();		  //with the root offset
		while(!cwd_name.empty())
			cwd_name.pop_back();

		if(path.size() == 1)
			return 0;

		path = path.substr(1, path.size() - 1); // get rid of the leading "/"
	}
		
	stringstream ss; //use a string stream to parse the path up
	ss.str(path);
	string temp;

	while(!ss.eof())
	{
		getline(ss, temp, '/');

		if(temp == ".")//current directory; do nothing
		{}
		else if(temp == "..")
		{
			if(cwd.size() > 1) //if we're already at root, do nothing, else pop an entry
			{
				cwd.pop();	   //off of the cwd stack to move up one level
				cwd_name.pop_back();
			}
		}
		else  // if not the current directory or parent dir
		{
			t = get_inode(temp.data()); //get the inode
			if(t == 0 || !t->dir) //if it doesn't exist, restore the cwd stack and drop out
			{
				cout << "No such directory." << endl;
				cwd = backup;
				cwd_name = name_backup;
				return -1;
			}
			else
			{
				cwd.push(t->location); //otherwise push the location on to the cwd stack
				cwd_name.push_back(t->name);
			}
		}
	}
	
	return 0;
} /////// end chdir() //////////////


// Return the offset of the inode of the dir or file specified (or 0 if not found).
// "Pathname" can be either relative or absolute.
unsigned int get_offset_from_path(const char * pathname)
{
	char fname[] = "get_offset_from_path()";

	unsigned int offset;
	string path(pathname); //Set up a string to hold the path
	stack<unsigned int> cwd_copy(cwd); //operate on a copy of the cwd so we don't affect it
	//deque<string> name_backup(cwd_name);
	Inode * t = new Inode();
		
	if(path[0] == '/') //check for absolute path
	{
		while(cwd_copy.size() > 1) //pop entries off the cwd stack until we're left
			cwd_copy.pop();		  //with the root offset
		         
		// if root was the entire path (caller wants offset to the root)
		if(path.size() == 1) {  // read in the offset of the root inode
			fs.type_read(ROOT_INODE_PTR_POSITION, &offset, fname);
			return offset;	
		}

		path = path.substr(1, path.size() - 1); // get rid of the leading "/"
	}
		
	stringstream ss; //use a string stream to parse the path up
	ss.str(path);
	string temp;

	while(!ss.eof())	{

		getline(ss, temp, '/');
		// cout << "\nNext part of the path is <" << temp << ">" << endl;

		if(temp == ".") //current directory
		{ 
			if(ss.eof()) {
				// Set the return inode now (since "." was the last part of the path given)
				unsigned int current_offset = cwd_copy.top();
				Inode* current_inode = new Inode;
				fs.fread(current_offset,(char*)current_inode, sizeof(Inode),fname);
				t = current_inode;
			}
		}
		else if(temp == "..") // parent dir
		{
			if(cwd_copy.size() > 1) //if we're already at root, do nothing, else pop an entry off to move up a level
			{
				cwd_copy.pop();
				// Set the return inode now (in case ".." was the last part of the path given)
				unsigned int parent_offset = cwd_copy.top();
				Inode* parent_inode = new Inode;
				fs.fread(parent_offset,(char*)parent_inode, sizeof(Inode),fname);
				t = parent_inode;
			}
		}
		else  // if not the current directory or parent dir
		{
			// search the "current" dir for the dir or file specified by the next part of the path
			t = get_inode_from_dirOffset( cwd_copy.top(), temp.data()); //get the inode
			if(t == 0 ) //if it doesn't exist, drop out
			{
				// cout << "\nNo such file or directory (reported from get_offset_from_path())." << endl;
				return 0;  // tell caller this was UNSUCCESSFUL
			}
			else
			{ 
				cwd_copy.push(t->location); //otherwise push the location on to the cwd stack
			}
		}
	} // end grabbing each part of the path
	
	return t->location; // return the ptr to the last part of the path

} //// end get_offset_from_path() //////


// Return the path string minus the last part. PROB WON'T WORK IF PATH == ROOT
string get_parent_path(const char* pathname)
{
	bool found_slash = false;
	string path = pathname;
	string parent_path;
	int length = strlen(pathname);

	// Churn through the pathaname 1 char at a time and flush the str so far to parent_path at each "/"
	for(int i = 0; i < length; i++) {

		if(path[i] == '/') {
			found_slash = true;
			parent_path = path.substr(0, i); // args: position, # chars
		}
	}
	// handle case like "/A"
	if(parent_path == "" ) {
		parent_path = "/";
	}
	// handle case like "file.txt"
	if(! found_slash) { // if no "/" at all in path, path is just a file in current dir (so parent is ".")
		parent_path = ".";  // parent is cwd
	}

	return parent_path;

} /// end get_parent_path() ////////////


// return the filename part of a pathname
string get_filename_from_path(const char* pathname)
{
	string filename;
	string path = pathname;
	int length = strlen(pathname);
	int i;
	// Start at back and churn toward beg. When hit first "/", flush it to filaname and quite
	//  (if never hit a "/", flush all)
	for( i = (length -1); i >= 0; i-- ) {
		if(path[i] == '/') {
			break; 
		}
	}
	filename = path.substr(i +1, (length - (i+1)) );  

	return filename;
} /// end get_filename_from_path() ////////////


/*

*/
int fs_link (const char * oldpath, const char * newpath)
{
	char* fname = "fs_link()";
	Inode* oldpath_inode = new Inode;
	Inode* newpath_inode = new Inode;
	Inode* parent_inode =  new Inode;  // for setting up the newpath file
	Inode * temp = new Inode();
	unsigned int parent_offset;
	string parent_path, newfile;  // newfile is the filename portion (minus path info)
	unsigned int oldpath_offset, newpath_offset;
	
	/////////////////////////////////////////////////////////
	//// Verify that source both exists and is not a dir ////
	oldpath_offset = get_offset_from_path(oldpath);

	if(oldpath_offset != 0 ) { // if oldpath exists
		fs.fread(oldpath_offset,(char*)oldpath_inode,sizeof(Inode),fname);
				//cout << "\nRead in oldpath_inode. Name <" << oldpath_inode->name << ">" << endl;
		if(oldpath_inode->dir) {
			cout << "\nSource path is a directory! Link command requires files only!" << endl;
			return -1;
		}
	}
	else { cout << "\nSource pathname is invalid.\n"; return -1;  }

	/////////////////////////////////////////////////////
	//// Verify that newpath does not already exist /////
	newpath_offset = get_offset_from_path(newpath);
			//cout << "\nnewpath_offset: " << newpath_offset << endl;
	// If newpath already exists
	if(newpath_offset != 0) {
		cout << "\nDestination pathname already exists! Link command will not overwrite existing files.\n"; 
		return -1; 
	}

	if(test_fs_link) cout << "\nLooks like Destination pathname is OK to proceed...\n";
	//////////////////////////////////
	//// carve space for new inode ///
	newpath_offset = carve(sizeof(Inode));
	//check for full disk
	if(newpath_offset == 0)	{	cout << "Out of disk space." << endl;		return -1;	}
	//////////////////////////////////////////////////////
	///// Go through steps to get the parent inode ///////

	// Get the parent path of the desired newpath file
	parent_path = get_parent_path(newpath);
	if(test_fs_link) cout << "\nParent path of <" << newpath << "> is <" << parent_path << ">\n";

	// Get the parent inode of the desired newpath file
	parent_offset = get_offset_from_path( parent_path.c_str() );
		
	// Verify parent inode exists
	if(parent_offset == 0 ) {
		cout << "\nParent of your desired newpath does not exist!";  return -1;
	}
	// Read in the parent inode.
	fs.fread(parent_offset,(char*) parent_inode,sizeof(Inode),fname);
	if(test_fs_link) cout << "Read in the parent.  Parent's name is <" << parent_inode->name << ">\n";
	//////////////////////////////////////////////////	
	//// Deal with parent/child/sibling pointers /////
	if(parent_inode->children == 0) //empty child list
	{
		parent_inode->children = newpath_offset;
		newpath_inode->prev = 0;  // "next" gets set below
		// Save the parent again
		fs.fwrite(parent_offset, (char*)parent_inode, sizeof(Inode), fname);
	}
	else //otherwise find the end of the list and insert as sibling
	{
					// Inode * temp = new Inode(); // declared above now (for testing)
		// Read in first child to start the traversal
		fs.fread(parent_inode->children, (char*)temp, sizeof(Inode), fname);
		// Iterate to the last child
		while(temp->next != 0)
			fs.fread(temp->next, (char*)temp, sizeof(Inode), fname);

		temp->next = newpath_offset; // attach this new sibling to the last child
		newpath_inode->prev = temp->location;
		// Save the previous sibling (new node gets saved below)
		fs.fwrite(temp->location, (char*)temp, sizeof(Inode), fname);
		// Also update the in-memory copy of oldpath_inode (from disk), in case it is the same as temp above
		//  (since insert_link_inode() below needs updated copy of oldpath_inode)
		fs.fread(oldpath_inode->location, (char*)oldpath_inode, sizeof(Inode), fname); 
	}
	///////////////////////////////////////////////////////////////////////////////
	//Populate the inode.  First handle fields that are unique to this new inode.
	newfile = get_filename_from_path(newpath);
		
	strcpy(newpath_inode->name, newfile.c_str());
	newpath_inode->location = newpath_offset;
	newpath_inode->next = 0; // "prev" gets set above
	newpath_inode->parent = parent_offset;
	newpath_inode->dir = false;
	newpath_inode->children = 0;
		
	// Fields that should be copies of the source inode
	newpath_inode->link_count    = oldpath_inode->link_count + 1; // increment link count
	newpath_inode->data          = oldpath_inode->data;
	newpath_inode->modified      = oldpath_inode->modified;
	newpath_inode->size          = oldpath_inode->size;
	newpath_inode->num_blocks    = oldpath_inode->num_blocks;
	newpath_inode->eof           = oldpath_inode->eof;
	newpath_inode->eof_block_pos = oldpath_inode->eof_block_pos;
	// Hook up pointers for the linked list of linked files
	insert_link_inode(oldpath_inode, newpath_inode);  

	// Save the new inode to disk
	fs.fwrite(newpath_offset,(char*)newpath_inode,sizeof(Inode),fname);

	// Update all links, using this new inode as the source for the updates
	update_all_links(newpath_inode);

	return 0; // indicate success
} ///// end fs_link() ////////

/*

*/
int fs_unlink (const char * filename)
{
	char* fname = "fs_unlink()";
	bool file_is_open = false;
	unsigned int path_offset;
	string file_only;

	Inode* inode = new Inode;
	Inode* prev_link_inode = new Inode;
	Inode* next_link_inode = new Inode;
	map<int, Oft_entry>::iterator it;  // key is file descriptor (from oft)

	// First verify that the file exists (assume filename may be a path)
	path_offset = get_offset_from_path(filename);

	if(path_offset == 0) {
		cout << "\nCannot unlink.  Filename \"" << filename << "\" does not exist!" << endl; 
		return -1;
	}

	// Read in the inode
	fs.fread(path_offset,(char*) inode, sizeof(Inode), fname);
	// Decrement the link count
	inode->link_count--;

	file_only = get_filename_from_path(filename);  

	// Check if file is open (traverse entire oft searching for it)
	for(it = oft.begin(); it != oft.end(); it++)
	{	
		// if the names match and the locations match
		if(strcmp(file_only.c_str(), it->second.inode->name) == 0 
			&& it->second.inode->location == inode->location)
		{
			file_is_open = true;
			// Decrement oft copy's link count so close() can know whether or not to call unlink 
			//  later to delete all data blocks.
			it->second.inode->link_count--; 
		}
	}


	if(inode->link_count > 0) {
		// No need to delete any data, just update all linked files about the change
		update_all_links(inode);

	}
	// If last link has been unlinked and file is not open, need to DELETE ALL DATA BLOCKS
	else if(! file_is_open) { 
		unsigned int block_offset = inode->data;
		unsigned int next_block_offset;

		// Read in the first "next" ptr
		fs.type_read(block_offset + BLOCK_NEXT_PTR_POS, &next_block_offset, fname);
		// Free the first block
		my_free(block_offset);

		// Free all other blocks
		while(next_block_offset != 0) {
			block_offset = next_block_offset;
			// Read in the next "next" ptr
			fs.type_read(block_offset + BLOCK_NEXT_PTR_POS, &next_block_offset, fname);
			// Free the current block
			my_free(block_offset);
		}
	}
	// return now if file is still open, since we need the inode to exist when it gets closed so it can be found
	if(file_is_open) return 0;

	//////////////////////////////////////////////////////
	///// Remove inode from linked-file list  ////////////
	//////////////////////////////////////////////////////
	/// Several Cases ///

	// If this inode is LAST LINK, then do nothing (the inode gets deleted below)
	if(inode->link_prev == 0  &&  inode->link_next == 0) {  }
	// If this inode is at the BEGINNING of the list
	else if(inode->link_prev == 0 ) {
		fs.fread(inode->link_next, (char*) next_link_inode, sizeof(Inode), fname);
		// Make the 2nd inode the 1st now
		next_link_inode->link_prev == 0;
		// Write the next inode back to disk
		fs.fwrite(next_link_inode->location, (char*) next_link_inode, sizeof(Inode), fname);
	}
	// If this inode is at the END of the list
	else if(inode->link_next == 0) {
		fs.fread(inode->link_prev, (char*) prev_link_inode, sizeof(Inode), fname);
		// Make the 2nd-to-last inode the last now
		prev_link_inode->link_next == 0;
		// Write the prev inode back to disk
		fs.fwrite(prev_link_inode->location, (char*) prev_link_inode, sizeof(Inode), fname);
	}
	// If this inode is in the MIDDLE of the list
	else {
		fs.fread(inode->link_next, (char*) next_link_inode, sizeof(Inode), fname);
		fs.fread(inode->link_prev, (char*) prev_link_inode, sizeof(Inode), fname);

		next_link_inode->link_prev = prev_link_inode->location;
		prev_link_inode->link_next = next_link_inode->location;

		fs.fwrite(next_link_inode->location, (char*) next_link_inode, sizeof(Inode), fname);
		fs.fwrite(prev_link_inode->location, (char*) prev_link_inode, sizeof(Inode), fname);
	}

	///////////////////////////////////////////////////////////
	//// Remove inode from parent and sibling lists ///////////
	///////////////////////////////////////////////////////////
	/// Several Cases ///

	// If this inode is LAST CHILD LEFT (only child), then alter the parent
	if(inode->prev == 0  &&  inode->next == 0) { 
		//////////////////////////////////////////////////////
		///// Go through steps to get the parent inode ///////
		Inode* parent_inode = new Inode;
		string parent_path = get_parent_path(filename);
		unsigned int parent_offset = get_offset_from_path(parent_path.c_str());
		// Verify the parent inode exists
		if(parent_offset == 0 ) {
			cout << "\nParent of your file does not exist!";  return -1;
		}
		// Read in the parent inode.
		fs.fread(parent_offset,(char*) parent_inode, sizeof(Inode), fname);
		parent_inode->children = 0; // Alter the parent
		// Save parent back to disk
		fs.fwrite(parent_offset,(char*) parent_inode, sizeof(Inode), fname);
	}
	// If this inode is the BEGINNING SIBLING, then make 2nd sibling the first
	else if( inode->prev == 0 ) {
		Inode* parent_inode = new Inode;
		Inode* sec_sibling_inode = new Inode;
		// Alter the parent so that its children ptr points to 2nd sibling

		//////////////////////////////////////////////////////
		///// Go through steps to get the parent inode ///////

		string parent_path = get_parent_path(filename);
		unsigned int parent_offset = get_offset_from_path(parent_path.c_str());
		// Verify the parent inode exists
		if(parent_offset == 0 ) {
			cout << "\nParent of your file does not exist!";  return -1;
		}
		// Read in the parent inode.
		fs.fread(parent_offset,(char*) parent_inode, sizeof(Inode), fname);

		// Read in the 2nd sibling
		fs.fread(inode->next,(char*) sec_sibling_inode, sizeof(Inode), fname);

		parent_inode->children = sec_sibling_inode->location; // Alter the parent
		sec_sibling_inode->prev = 0;  // Make the 2nd sibling become the first
		// Save parent and 2nd sibling back to disk
		fs.fwrite(parent_offset,(char*) parent_inode, sizeof(Inode), fname);
		fs.fwrite(sec_sibling_inode->location,(char*) sec_sibling_inode, sizeof(Inode), fname);
	}
	// If this inode is the LAST SIBLING
	else if( inode->next == 0 ) {
		Inode* prev_inode = new Inode;
		// Alter the 2nd-to-last sibling so that it becomes the last sibling
		
		fs.fread(inode->prev, (char*) prev_inode, sizeof(Inode), fname);
		prev_inode->next = 0;
		fs.fwrite(inode->prev, (char*) prev_inode, sizeof(Inode), fname);
	}
	// If this inode is in the MIDDLE of the sibling list
	else {
		Inode* prev_inode = new Inode;
		Inode* next_inode = new Inode;
		//read in the adjacent inodes in the list, point them to each other & write em back out
		fs.fread(inode->prev, (char*)prev_inode, sizeof(Inode), fname);
		fs.fread(inode->next, (char*)next_inode, sizeof(Inode), fname);
		prev_inode->next = next_inode->location;
		next_inode->prev = prev_inode->location;
		fs.fwrite(inode->prev, (char*)prev_inode, sizeof(Inode), fname);
		fs.fwrite(inode->next, (char*)next_inode, sizeof(Inode), fname);
	}

	
	// Free the memory used for the inode of the unlinked inode
	my_free(inode->location);

	return 0; // indicate success

} //// end fs_unlink() //////

/*
This function takes to arguments, the path of the 
source file and the path of the destination.
The data of the source is then copied to the newly
created destination.
The source must exist, and the destination must not.
The two paths may both be relative or absolute.
On success, returns 0.
On failure, returns-1.
*/
int fs_copy(const char * src, const char * dest)
{
	char * fname = "fs_copy()";
	Inode * src_inode = new Inode;
	Inode * dest_inode = new Inode;
	Inode * parent_indoe = new Inode;
	string parent_path, newfile;
	unsigned int src_offset, dest_offset, dest_parent_offset;
	char buffer;

	//Check if src exists
	src_offset = get_offset_from_path(src);
	if(src_offset != 0)
	{
		fs.fread(src_offset, (char*) src_inode, sizeof(Inode), fname);
		if(src_inode->dir)
		{
			cout << "Source is not a file." << endl;
			return -1;
		}
	}
	else
	{
		cout << "Source does not exist." << endl;
		return -1;
	}
	
	//Make sure dest does not exist
	dest_offset = get_offset_from_path(dest);
	if(dest_offset != 0)
	{
		cout << "Destination already exists." << endl;
		return -1;
	}

	//Get the parent offset for the dest
	parent_path = get_parent_path(dest);
	dest_parent_offset = get_offset_from_path(parent_path.data());

	//Create the destination file
	newfile = get_filename_from_path(dest);
	cwd.push(dest_parent_offset);
	int dest_fd = fs_open(newfile.data(), FS_O_RDWR);
	cwd.pop();

	//Open the src file for reading
	cwd.push(src_inode->parent);
	int src_fd = fs_open(src, FS_O_RDWR);
	cwd.pop();

	fs_seek(src_fd, 0);
	
	//Copy over the data
	while(oft[src_fd].d_offset != src_inode->eof)
	{
		fs_read(src_fd, &buffer, 1);
		fs_write(dest_fd, &buffer, 1);
	}

	//Close the files
	fs_close(src_fd);
	fs_close(dest_fd);

	//Success!
	return 0;
}

/*

*/
int fs_stat (const char * filename, fileStat *buf)
{
	char * fname = "fs_stat()";
	//Inode * temp = new Inode();
	Inode * inode = new Inode();

	inode = get_inode(filename);
	// Handle file not found
	if( inode == 0 ) {
		cout << "Could not stat file \"" << filename << "\": file not found in current working directory." 
			   << endl; 
		return -1;
	}
	// Fill up the user's fileStat struct
	strcpy(buf->name, inode->name );
	buf->is_dir = inode->dir;
	buf->size   = inode->size;
	buf->num_blocks = inode->num_blocks;
	buf->modified = inode->modified;
	buf->link_count = inode->link_count;

	// Print the info to screen (for users of the Shell command)
	//  Use the buf as source for verification of correct copying into the buf
	cout << "\nFile status info: \n";
	cout << "\tName: \"" << buf->name << "\"" << endl;
	cout << "\tDirectory?: " << ((buf->is_dir == 0) ? "False" : "True") << endl
		<< "\tSize in bytes (Size of inode for dirs): "<< buf->size << endl
		<< "\tNumber of data blocks: " << buf->num_blocks << endl
		<< "\tModified date: " << ctime(&(buf->modified)) // no endl since ctime() includes "\n"
		<< "\tNumber of links (1 means only 1 inode): " << buf->link_count << endl;

	return 0; // upon success
} ////// end fs_stat() ////////

/*
This function imports a file from the user's physical hard drive into the filesystem
*/
int fs_import(const char * src, const char * dest)
{
	fstream in;
	string contents;
	char buffer;

	in.open(src, ios_base::in);
	Inode * inode = get_inode(dest);
	
	if(in.fail())
	{
		cout << "Source does not exist." << endl;
		return -1;
	}
	else if(inode != 0)
	{
		cout << "Destination already exists." << endl;
		return -1;
	}
	else
	{
		//grab the contents of the file
		while(!in.eof())
		{
			in.get(buffer);
			contents += buffer;
		}
		contents = contents.substr(0, contents.size() - 1);
		
		//create a new file and write the contents into it
		int fd = fs_open(dest, FS_O_RDWR);
		fs_write(fd,contents.data(),contents.size());
		fs_close(fd);

		return 0;
	}
}

/*
This function exports a file from the filesystem onto the user's physical harddrive
*/
int fs_export(const char * src, const char * dest)
{
	ofstream out;

	Inode * inode = get_inode(src);
	if(inode == 0)
	{
		cout << "Source does not exist.";
		return -1;
	}
	else
	{
		out.open(dest);
		char buffer;

		int fd = fs_open(src, FS_O_RDONLY);
		while(oft[fd].d_offset != inode->eof)
		{
			fs_read(fd, &buffer, 1);
			out << buffer;
		}
		fs_close(fd);
		out.close();
	}
}


/*
 For our own testing. Useful when you want stat info about a file not in cwd (and you don't have
  path info), and you already have ptr to the inode.
*/
void stat_inode(Inode* inode)
{

	cout << "\nFile status info: \n";
	cout << "\tName: \"" << inode->name << "\"" << endl;
	cout << "\tDirectory?: " << ((inode->dir == 0) ? "False" : "True") << endl
		<< "\tSize in bytes (Size of inode for dirs): "<< inode->size << endl
		<< "\tNumber of data blocks: " << inode->num_blocks << endl
		<< "\tModified date: " << ctime(&(inode->modified)) // no endl since ctime() includes "\n"
		<< "\tNumber of links (1 means only 1 inode): " << inode->link_count << endl;
} ////// end stat_inode() ////////



/*
This function facilitates the "ls" command (not recursive-- current dir only)
*/
int print_current_directory()
{
	char * fname = "print_current_directory()";
	Inode * temp = new Inode();
	Inode * inode = new Inode();

	cout << ".\n..\n";
	
	//get the cwd's inode
	fs.fread(cwd.top(), (char*)inode, sizeof(Inode), fname);

	//if there are children (of cwd), iterate through the list, printing each name
	if(inode->children != 0)
	{
		fs.fread(inode->children, (char*)temp, sizeof(Inode), fname);
		cout << temp->name << endl;

		while(temp->next != 0)
		{
			fs.fread(temp->next, (char*)temp, sizeof(Inode), fname);
			cout << temp->name << endl;
		}
	}
	
	return 0;
} ///////// end print_current_directory() ///////////////

/*
This function facilitates the "tree" command. This func takes no args to match Dr. Cao's,
specificiations.  The real work gets done by print_dir_recur() below.
*/
void print_directory()
{
	char * fname = "print_directory()";

	Inode* inode = new Inode();
	Inode* child_inode;  // instantiated below if needed
	unsigned int child_offset;
	string tabs = ""; // start with no tabs in the output (top-level of the tree)
	//get the cwd's inode to start the recursion from
  fs.fread(cwd.top(), (char*)inode, sizeof(Inode), fname);

	////////////////////////////////////////////////////////////////////////////////////////////
	///// INITIALIZING THE RECURSION: Print CWD info, then try to go "downward" recursively ////
	
	// Printing section
	cout << endl << tabs << inode->name << endl; 

	// Start the recursion
	child_offset = inode->children;
	// Try to go "downward" in the tree
	if(child_offset != 0 ) {
		child_inode = new Inode;
		// read the child
	  fs.fread(child_offset, (char*)child_inode, sizeof(Inode), fname);
		// recur to this child (the recursive func will try to go to it's siblings too)
		print_dir_recur(child_inode, tabs + "\t");
	}

} ///////// end print_directory() ///////////////


// The recursive (workhorse) part of implementation of "tree" command.
void print_dir_recur(Inode * parent_inode, string tabstr)
{
  char * fname = "print__dir_recur()";
	unsigned int child_offset, sibling_offset;
	Inode* child_inode;
	Inode* sibling_inode;

	// Printing section
	cout << tabstr << parent_inode->name;
	// If this is a file, we must print its size
	if(! parent_inode->dir) {
		cout << "  Size: " << parent_inode->size << " bytes" << endl;
	}
	else{	cout << endl; } // don't print size of dirs


	// RECURSIVE section
	child_offset = parent_inode->children;
	// Try to go "downward" in the tree
	if(child_offset != 0 ) {
		child_inode = new Inode;
		// read the child
	  fs.fread(child_offset, (char*)child_inode, sizeof(Inode), fname);
		// recur to this child
		print_dir_recur(child_inode, tabstr + "\t");
	}
	// Try to go "across" (to siblings)
	sibling_offset = parent_inode->next;
	sibling_inode = parent_inode; // reusing memory, but making the name more meaningful.

	while(sibling_offset != 0 ) {
		  
		  // read the next sibling
		  fs.fread(sibling_offset, (char*)sibling_inode, sizeof(Inode), fname);
			// recur to this sibling
		  print_dir_recur(sibling_inode, tabstr);
			// update to the next sibling
			sibling_offset = sibling_inode->next;
	}

} ///////// end print_dir_recur() ///////////////


/*
  For our testing. Prints the directory structure from the given path in a tree format,
	and prints stat-like info about files (but not dirs).
*/
void tree_stat(const char* path)
{
	char * fname = "tree_stat()";

	Inode* inode = new Inode();
	Inode* child_inode;  // instantiated below if needed
	unsigned int child_offset;
	unsigned int path_offset;
	string tabs = ""; // start with no tabs in the output (top-level of the tree)
	
	// Turn the path given into an offset
	path_offset = get_offset_from_path(path);
	
	//get the inode to start the recursion from
  fs.fread(path_offset, (char*)inode, sizeof(Inode), fname);

	///////////////////////////////////////////////////////////////////////////////////////////
	//// INITIALIZING THE RECURSION: Print first dir info, then try to go "downward" recursively ////
	
	// Printing section
	cout << endl << tabs << "\""<< inode->name << "\"" << endl; // assumes path is a dir (so no metadata printed)
	
	// Start the recursion
	child_offset = inode->children;
	// Try to go "downward" in the tree
	if(child_offset != 0 ) {
		child_inode = new Inode;
		// read the child
	  fs.fread(child_offset, (char*)child_inode, sizeof(Inode), fname);
		// recur to this child (the recursive func will try to go to it's siblings too)
		tree_stat_recur(child_inode, tabs + "   ");
	}

} ////// end tree_stat() /////////

// The recursive (workhorse) part of implementation of "tree_stat" command.
void tree_stat_recur(Inode* parent_inode, string tabstr)
{
	char * fname = "tree_stat_recur()";
	unsigned int child_offset, sibling_offset;
	Inode* child_inode;
	Inode* sibling_inode;

	// Printing section
	cout << tabstr << "\""<< parent_inode->name << "\"" << endl;
	// If this is a file, print extensive info
	if(! parent_inode->dir) {
	
		cout << tabstr;  
		print_spaces(5);

		// Shorten the human-readable version of the time (for formatting reasons)
		string modtime = ctime(&(parent_inode->modified));
		modtime = modtime.substr(4, 15);

		printf("%12s%-5d  %12s%-15s  %12s%-10d", "Size:", parent_inode->size, "Modified:",
			modtime.c_str(), "Data offset:", parent_inode->data);
		cout << endl;
		cout << tabstr;  
		print_spaces(5);

		printf("%12s%-5d  %12s%-15d  %12s%-10d", "Num blocks:", parent_inode->num_blocks, "eof:",
			parent_inode->eof, "eof_blckpos:", parent_inode->eof_block_pos );
		cout << endl;
		cout << tabstr;  
		print_spaces(5);

		printf("%12s%-5d", "Link count:", parent_inode->link_count);
		
		cout << endl;
		cout << tabstr;  
		print_spaces(5);
		cout << "Linkd files:  ";
		// Traverse through all links to print their name 
		print_linked_names(parent_inode);

		cout << endl << endl;
	}

	// RECURSIVE section
	child_offset = parent_inode->children;
	// Try to go "downward" in the tree
	if(child_offset != 0 ) {
		child_inode = new Inode;
		// read the child
	  fs.fread(child_offset, (char*)child_inode, sizeof(Inode), fname);
		// recur to this child
		tree_stat_recur(child_inode, tabstr + "   ");
	}
	// Try to go "across" (to siblings)
	sibling_offset = parent_inode->next;
	sibling_inode = parent_inode; // reusing memory, but making the name more meaningful.

	while(sibling_offset != 0 ) {
		  
		  // read the next sibling
		  fs.fread(sibling_offset, (char*)sibling_inode, sizeof(Inode), fname);
			// recur to this sibling
		  tree_stat_recur(sibling_inode, tabstr);
			// update to the next sibling
			sibling_offset = sibling_inode->next;
	}

} ////// end tree_stat_recur() /////////


/*
   Helper for tree_stat.  Used for formatting.
*/
void print_spaces(int num_spaces)
{

	for(int i = 0; i < num_spaces; i++) {
		cout << " ";
	}
}

/*
  Traverse through all links connected to the given inode and print their names
*/
void print_linked_names(Inode* source_inode)
{
	char* fname = "print_linked_names()";
	char dummy[MAX_FILENAME_SZ];
	Inode* inode = new Inode;
	// Initialize temp inode
	deep_copy_inode(source_inode, inode);

	// Go to the beginning of the list (so we will update all inodes)
	while(inode->link_prev != 0)
		fs.fread(inode->link_prev, (char*)inode, sizeof(Inode), fname);
	// Print first name
	if(inode->link_next == 0)
		// printf("%-8s", inode->name);
		printf("%s  ", inode->name);
	else {
		strcpy(dummy, inode->name);
		strcat(dummy, ",");
		// printf("%-8s", dummy);
		printf( "%s  ", dummy );
	}
	// Print out all other names
	while(inode->link_next != 0) {
		// Read in next inode into "inode"
		fs.fread(inode->link_next, (char*)inode, sizeof(Inode), fname);
		if(inode->link_next == 0)
			// printf("%-8s", inode->name);
			printf("%s  ", inode->name);
		else {
			strcpy(dummy, inode->name);
			strcat(dummy, ",");
			// printf("%-8s", dummy);
			printf( "%s  ", dummy );
		}
	}

} ///// end print_linked_names() /////////



/*
This function searches the cwd for the inode of a file or directory
and returns it.  If it doesn't exist, it returns 0.
*/
Inode * get_inode(const char * name)
{
	char fname[] = "get_inode()";
	Inode * c = new Inode();

	// read in the current Directory
	fs.fread(cwd.top(),(char*)c, sizeof(Inode), fname);
	// try to get the inode being searched for (child of the current dir)
	if(c->children != 0)
	{
		fs.fread(c->children,(char*)c, sizeof(Inode), fname);
			if(strcmp(c->name, name) == 0)
				return c;
		do
		{

			fs.fread(c->next,(char*)c, sizeof(Inode), fname);
			if(strcmp(c->name, name) == 0)
				return c;

		}while(c->next != 0);
	}

	return 0;

}


// Helper for get_offset_from_path().  Similar to get_inode(), except it searches the directory 
//  specified by the "dir_offset" (rather than just the cwd) for the file or directory specified
//  by "filename". If filename doesn't exist or if dir_offset actually refers to a file, it returns 0.
Inode * get_inode_from_dirOffset(unsigned int dir_offset, const char * filename)
{
	char fname[] = "get_inode_from_dirOffset()";
	Inode * c = new Inode();

	// read in the  Directory specified by dir_offset
	fs.fread(dir_offset,(char*)c, sizeof(Inode), fname);
	// try to get the inode being searched for (child of the dir read in)
	if(c->children != 0)
	{
		fs.fread(c->children,(char*)c, sizeof(Inode), fname);
			if(strcmp(c->name, filename) == 0)
				return c;
		do
		{

			fs.fread(c->next,(char*)c, sizeof(Inode), fname);
			if(strcmp(c->name, filename) == 0)
				return c;

		}while(c->next != 0);
	}

	return 0; // if not found

} //// end get_inode_from_dirOffset() ///////


/*
  Inserts "new_inode" into the linked list of linked files linked to "old_inode". 
	The "old_inode" must already have its link_prev and link_next fields set. 
	The func uses the link_next and link_prev fields of "old_inode" to navigate the list.
*/
void insert_link_inode(Inode* old_inode, Inode* new_inode)
{
	char* fname = "insert_link_inode()";
	
	// Get to the end of the list of linked files
	while(old_inode->link_next != 0)
		fs.fread(old_inode->link_next, (char*)old_inode, sizeof(Inode), fname);

	old_inode->link_next = new_inode->location; // attach this new link sibling
	new_inode->link_prev = old_inode->location;
	new_inode->link_next = 0;  // newly inserted node is end of the last
	// Save the previous link sibling
	fs.fwrite(old_inode->location, (char*)old_inode, sizeof(Inode), fname);
	// Save the new link sibling
	fs.fwrite(new_inode->location, (char*)new_inode, sizeof(Inode), fname);

} /////// end insert_link_inode() /////////////


/*
  Updates all relavant file metadata (size, num_blocks, eof, eof_block_pos, modified, link_count, etc)
	of all files that are linked to the "source_inode" file.  It uses the metadata of "source_inode"
	as the source of the metadata (sets all other linked files metadata to the same as it).
*/
void update_all_links(Inode* source_inode)
{
	char* fname = "update_all_links()";
	Inode* inode = new Inode;
	// Initialize temp inode
	deep_copy_inode(source_inode, inode);

	// Go to the beginning of the list (so we will update all inodes)
	while(inode->link_prev != 0)
		fs.fread(inode->link_prev, (char*)inode, sizeof(Inode), fname);

	// Update all inodes using relavant link metadata of source_inode
	
	// Update the first inode in the list
	update_one_link(source_inode, inode);
	// Save the updated inode to disk
	fs.fwrite(inode->location, (char*)inode, sizeof(Inode), fname);

	if(test_update_all_links) {
		cout << "\nJust updated linked file: \n";
		fileStat* buf = new fileStat;
		// fs_stat(inode->name, buf);
		stat_inode(inode);
	}

	// Update the rest of the inodes in the link-list
	while(inode->link_next != 0) {
		// Read in next inode into "inode"
		fs.fread(inode->link_next, (char*)inode, sizeof(Inode), fname);
		update_one_link(source_inode, inode);
		// Save the updated inode
		fs.fwrite(inode->location, (char*)inode, sizeof(Inode), fname);

		if(test_update_all_links) {
			cout << "\nJust updated linked file: \n";
			fileStat* buf = new fileStat;
			// fs_stat(inode->name, buf);
			stat_inode(inode);
		}
	}
} ///////// end update_all_links() //////////


// Helper for update_all_links().  Only writes to memory (caller must still save to disk).
void update_one_link(Inode* source_inode, Inode* dest_inode)  
{
	// Fields that should be copies of the source inode
	dest_inode->link_count    = source_inode->link_count; 
	dest_inode->data          = source_inode->data;
	dest_inode->modified      = source_inode->modified;
	dest_inode->size          = source_inode->size;
	dest_inode->num_blocks    = source_inode->num_blocks;
	dest_inode->eof           = source_inode->eof;
	dest_inode->eof_block_pos = source_inode->eof_block_pos;
} ///////// end update_one_link() //////////


/*
  Makes a deep copy of source_inode into dest_inode (copies all fields). 
	Requires both	inodes to have already been allocated.  Used in update_all_links(), etc.
*/
void deep_copy_inode(Inode* source_inode, Inode* dest_inode)
{
	strcpy(dest_inode->name, source_inode->name);
	dest_inode->location = source_inode->location;
	dest_inode->next     = source_inode->next; 
	dest_inode->prev     = source_inode->prev; 
	dest_inode->parent   = source_inode->parent;
	dest_inode->dir      = source_inode->dir;
	dest_inode->children = source_inode->children;

	dest_inode->link_count    = source_inode->link_count; 
	dest_inode->data          = source_inode->data;
	dest_inode->modified      = source_inode->modified;
	dest_inode->size          = source_inode->size;
	dest_inode->num_blocks    = source_inode->num_blocks;
	dest_inode->eof           = source_inode->eof;
	dest_inode->eof_block_pos = source_inode->eof_block_pos;

	dest_inode->link_next     = source_inode->link_next;
	dest_inode->link_prev     = source_inode->link_prev;
} //////// end deep_copy_inode() /////


/*
Prints out the full path of the current working
directory.
*/
void pwd(ostream & out)
{
	out << "/";
	
	for(int i = 0; i < cwd_name.size(); i++)
		out << cwd_name[i] << "/";

	out << endl;
}

/*
Creates an empty file of a user-specified size.
The data is allocated in blocks of size, BLOCK_SZ,
and are linked together as in a doubly linked list.
On success, returns 0.
On failure, returns -1.
*/
unsigned int create_file(const char * file_name, int size)
{
	char * fname = "create_file()";
	int bytes_still_needed = size;  // for dealing with allocating blocks
	unsigned int next_block_offset;
	unsigned int prev_block_offset;

	//carve space for new inode
	unsigned int offset = carve(sizeof(Inode));
	//check for full disk
	if(offset == 0)	{		cout << "Out of disk space." << endl;		return -1;	}
	//get cwd inode
	Inode * c = new Inode();   // for current directory
	Inode * n = new Inode();  // for new file
	fs.fread(cwd.top(), (char*)c, sizeof(Inode), fname);
	
	// Deal with parent/child/sibling pointers
	if(c->children == 0)//empty child list
	{
		c->children = offset;
		n->prev = 0;   // "next" gets set below
		fs.fwrite(cwd.top(), (char*)c, sizeof(Inode), fname);
	}
	else //otherwise find the end of the list
	{
		Inode * temp = new Inode();
		fs.fread(c->children, (char*)temp, sizeof(Inode), fname);

		while(temp->next != 0)
			fs.fread(temp->next, (char*)temp, sizeof(Inode), fname);

		temp->next = offset;
		n->prev = temp->location;  // "next" gets set below
		fs.fwrite(temp->location, (char*)temp, sizeof(Inode), fname);
	}
	
	//Populate the inode ("data" and "eof" get set below)
	strcpy(n->name, file_name);
	n->location = offset;
	n->next = 0;   // "prev" gets set above
	n->parent = cwd.top();
	n->dir = false;
	n->modified = time(0);
	// n->size = size + FILE_SEG_INFO_SIZE;
	n->size = 0;    // will increment this with each successfull block allocation
	n->children = 0;
	n->link_count = 1;
	n->num_blocks = 1;
	n->eof_block_pos = FILE_SEG_INFO_SIZE;  
	n->link_next  = 0;
	n->link_prev  = 0;
	//////////////////////////////////////////////////////////////////////////////////////////
	// Allocate one block at a time until we have a total file large enough for user's size //

	// get first block
	n->data = carve(BLOCK_SZ);
	n->eof = n->data + FILE_SEG_INFO_SIZE;

	//check for full disk
	if(n->data == 0)	{		cout << "Out of disk space." << endl;		return -1;	}
	n->size += BLOCK_SZ;
	// write to disk the ptrs for this first block
	fs.type_write(n->data + BLOCK_PREV_PTR_POS, 0, fname);  // write the ptr to the prev block ("0" is null)
	fs.type_write(n->data + BLOCK_NEXT_PTR_POS, 0, fname);  // write the ptr to the next block
	
	// Fill a memory buffer with (BLOCK_SZ - info size) bytes in preparation for writing to disk
	char * buff = new char[BLOCK_SZ - FILE_SEG_INFO_SIZE];
	for(int i = 0; i < (BLOCK_SZ - FILE_SEG_INFO_SIZE); i++)
		buff[i] = 0;
	// write the data bytes for this block to disk
	fs.fwrite(n->data + FILE_SEG_INFO_SIZE, buff, (BLOCK_SZ - FILE_SEG_INFO_SIZE), fname); 

	next_block_offset = n->data; // prepare for adding another block
	bytes_still_needed -= (BLOCK_SZ - FILE_SEG_INFO_SIZE);
	// Get more blocks until we've satisfied user's request
	while( bytes_still_needed > 0 ) {

		//cout << "\nstarting another block allocation section.  bytes_still_needed: " << bytes_still_needed<< endl;
		
		prev_block_offset = next_block_offset;
		// get next block
		next_block_offset = carve(BLOCK_SZ);
		//check for full disk
		if(next_block_offset == 0)	{cout << "Out of disk space." << endl;	return -1;	}
		
		// Hook up ptrs between the blocks (by writing to disk)
		fs.type_write((prev_block_offset + BLOCK_NEXT_PTR_POS), next_block_offset, fname);  
		fs.type_write((next_block_offset + BLOCK_PREV_PTR_POS), prev_block_offset, fname);  
		// write the new block's next ptr as null
		fs.type_write((next_block_offset + BLOCK_NEXT_PTR_POS), 0, fname);  // write the ptr to the next block
	
		// write the data bytes for this block to disk
		fs.fwrite((next_block_offset + FILE_SEG_INFO_SIZE), buff, (BLOCK_SZ - FILE_SEG_INFO_SIZE), fname); 
		
		n->size += BLOCK_SZ;
		(n->num_blocks)++;
		bytes_still_needed -= (BLOCK_SZ - FILE_SEG_INFO_SIZE);
	} // end while more bytes are still needed to create a file large enough
	
	//write out the new file inode
	fs.fwrite(n->location, (char*)n, sizeof(Inode), fname);
	
	
} //// end create_file() ////


/* ///////////////////////////////////////////////////////////
   /// CARVE functions ///////////////////////////////////////
		Created Date:  2/14/11
		Author:      Jason Frank

		Purpose: Basically mimics what malloc() and free() do for the memory, but do it on disk.
		         Unlike malloc, this does not do buffering.  Note that this file includes a coalesce
						 function that can be called anytime free() is called.
*/

// Function: find_big_enough_node()
// Purpose:  traverses the free-list to try to find a node with enough mem for user's request
// Parameters: 1) total mem needed (including bookkeep) 
// Returns: Ptr to the first such node (0 if there is no such node)
unsigned int find_big_enough_node( long entire_chunk, FList_node* caller_node, bool& found  )
{
	//FList_node f;
	char* func_name = "find_big_enough_node()";
	unsigned int offset = 0; // for found node
	FList_node* f = new FList_node;

	if(free_head == 0  ||  free_list_empty == true) {
		cout << "\n\nInternal function \"carve()\" issues the following ERROR: "
			   << "\nNo more free memory available (free list is empty).\n" << endl;
		found = false;
		return 0;
	}

	offset = free_head;

	read_flist_nd(offset, f, func_name);
	//offset = f->flink;

	// advance to next node while the current node is not big enough & there is a next node
	while( f->flink != 0   &&   f->size < entire_chunk )  {   
		offset = f->flink;  // make the next node the "current" node
		// read in the next node into f
		read_flist_nd(f->flink, f, func_name);
	}
  // if we're at the last node and we still haven't found one large enough
	if( f->flink == 0  &&  f->size < entire_chunk ) { found = false; return 0;  }
	else  {  
		found = true;   
		// fill in the caller's node for their convenience
		caller_node->size = f->size;    
		caller_node->flink = f->flink;
		caller_node->blink = f->blink;
		return offset;   // "ptr" to the found node
	}

} //////////// end function find_big_enough_node() ////////////////////


// Function: carve()
// Purpose:  workhorse function allocates memory like malloc(), but from disk (and no buffering)
// Parameters: 1) number of bytes requested
// Returns:  "ptr" to the memory allocated (offset from beg of file system), 
//            or 0 on error (i.e., not enough memory could be found)
unsigned int carve( unsigned int size )
{
  //unsigned long* mem;
	//unsigned long* usermem;
	char* func_name = "carve()";
	unsigned int mem_offset;
	unsigned int usermem_offset;
	FList_node *f  = new FList_node; 
	FList_node *f2 = new FList_node;
  unsigned int entire_chunk; 
	unsigned int user_chunk_size;
  //long allocated; 
	bool found = false;  // indicates whether or not a node large enough was found
	unsigned int found_nd_offset;


  // get user's size aligned to an 8 byte multiple
	if( size % 8 != 0 ) { size += 8 - (size % 8);  }
  entire_chunk = size + BOOKKEEP;

	//if( test_mal ) { say "-------------------------------------");  }
	//if( test_mal ) { say "\nAt begin of malloc(), after manip, user's size is: <%d>.  "\
	//				             " sbrk(0) is: <0x%lx>\n", size, ULI sbrk(0) ); }


	// find a Free-list node with sufficient size	that we could carve off user's mem	
	found_nd_offset = find_big_enough_node( entire_chunk, f, found );  // need 12 extra bytes for node's fields

  if( found ) {       // if we have a node large enough to grant user's request

		             // allocated = 0;  // from legacy mymalloc code... not sure if needed yet
		// If there will be a Free-List node leftover after dolling out user's mem from this node
  	if( entire_chunk <= (f->size - FNODE_SIZE ) ) {
			// carve memory off the BACK of the node to give to user
			// mem = ((unsigned long*) f) + (f->size - entire_chunk)/sizeof(int); // beg spot of user's chunk
			mem_offset = found_nd_offset + (f->size - entire_chunk); // beg spot of user's chunk
			
			user_chunk_size = entire_chunk;  // set the user's entire mem chunk size
			// write the user's chunk-size to disk
			fs.type_write(mem_offset, user_chunk_size, func_name );

			// reflect the node's change of size 
			f->size -= entire_chunk;
			// update node's change of size on disk 
			fs.type_write(found_nd_offset, f->size, func_name );
		}
		else {  // If NOT, then just give user this entire node's memory (delete the node too)
         //			mem = (unsigned long*) f;  // beg spot of user's chunk will just be beg of node
			mem_offset = found_nd_offset;  // beg spot of user's chunk will just be beg of node

         //			f2 = (FList_node) mem;   // get ready to set the user's mem chunk size
         //     delete_node( f );            // delete this node since we gave user all it's memory
         //			f2->size = f->size;				// set the user's entire mem chunk size

			user_chunk_size = f->size;  // set the user's entire mem chunk size (they just get all of free node)
			// write the user's chunk-size to disk
			fs.type_write(mem_offset, user_chunk_size, func_name );

			delete_node( f );            // delete this node since we gave user all it's memory
		}
		usermem_offset = mem_offset + BOOKKEEP;
	}	// end if we have a node large enough 

	else {   // if we DO NOT have a node large enough 
		
		return 0;  // indicates we cannot satisfy user's request for disk space
	}
	
	return usermem_offset;		
} /////////////// end my_malloc() ////////////////////////////////////


// Function: delete_node()
// Purpose:  Deletes a node from the free-list by properly changing needed pointers
// Parameters: 1) Ptr to Free-list node to be deleted
void delete_node( FList_node* f )
{		
	char* func_name = "delete_node()";
	FList_node* f_blink_nd_ptr = new FList_node;   // for this program, equiv to "f->blink"
	FList_node* f_flink_nd_ptr = new FList_node;
	/*
  if( test_mal) { 
		say "\nINSIDE DELETE(0x%lx), f: <0x%lx>  ", ULI f, ULI f ); 
		if( f->blink != NULL ) say "  f->blink: <0x%lx>,  ", ULI f->blink );
		if( f->flink != NULL ) say "  f->flink: <0x%lx>,  ", ULI f->flink );
	}
	*/

	// handle case of this is the only node left
	if( f->blink == 0  &&  f->flink == 0 ) {
		free_head = 0;   // equivalent to NULL for this program
		free_list_empty = true;
		cout << "\n\nInternal function \"carve()\" issues the following WARNING: "
			   << "\nThe last of the free space on this file system was just used."
			   << "\nYour next command that requires new disk space will fail.\n" << endl;
		return;
	}
  // if this is not the first node of the list: change a field of blink node
	if( f->blink != 0 ) {	
		// get f->blink node from disk into memory, as "f_blink_nd_ptr"
		read_flist_nd(f->blink, f_blink_nd_ptr, func_name );
		f_blink_nd_ptr->flink = f->flink;
		// mymalloc code:   f->blink->flink = f->flink;

		// write the changed blink node back to disk
		write_flist_nd(f->blink, f_blink_nd_ptr, func_name );
	}
	else  {   // if this is the first node of the list
	  free_head =  f->flink;  // then set the new first node as first node of list
	}
	// If this is not the last node of the list: change a field of flink node
	if( f->flink != 0 ) {
		// get f->blink node from disk into memory, as "f_blink_nd_ptr"
		read_flist_nd(f->flink, f_flink_nd_ptr, func_name );
		f_flink_nd_ptr->blink = f->blink;
		// mymalloc code:  f->flink->blink = f->blink;

		// write the changed flink node back to disk
		write_flist_nd(f->flink, f_flink_nd_ptr, func_name );
	}
} ///////////// end function  delete_node()  //////////////////


// Function: my_free()
// Purpose:  Mimics the real free() by putting user's memory onto the free-list on disk
// Parameters:  User's "ptr" to memory chunk to be freed (offset to beg of fs)
void my_free( unsigned int user_offset )
{
  //FListptr f = (FListptr) ptr;
  //FListptr new_node_head;
	unsigned int new_node_offset; // beg of node to be put back on free list (accounts for BOOKEEP bytes)

  new_node_offset = user_offset - BOOKKEEP;		

  /*if( test_free ) { say "\nInside my_free(0x%lx),  ", ULI f );
		// say "\nAbout to call  add_node(0x%lx);\n", ULI (f - BOOKKEEP/sizeof(int)) );		
		say "\nAbout to call  add_node(0x%lx);", ULI new_node_head );		
	}*/
	add_node( new_node_offset );		

  // if( test_free ) { say "\nAt end of my_free(0x%lx) \n", ULI f );    }
} ///////////////////// end function my_free() //////////////////////////


// Function: add_node()
// Purpose:  adds a node to the beginning of the free-list by properly changing pointers
// Parameters: 1) Ptr to Free-list node to be added
void add_node( unsigned int new_node_offset)
{ 
	char* func_name = "add_node()";
	/*
  if( test_free ) { say "\n\nAt beg of add_node(0x%lx),  free_list_begin(): <0x%lx>,  "\
			                  , ULI f, ULI free_list_begin() );
	} */
	unsigned int oldfirst_node_offset; 
	FList_node* oldfirst_node = new FList_node;
	FList_node* newfirst_node = new FList_node;
	// get offset to oldfirst_node from disk into memory
	fs.type_read(FREE_HEAD_PTR_POSITION, &oldfirst_node_offset, func_name );

	// if there is already a free-list node
	if( free_head != 0  &&  !free_list_empty)  {
			// Change old first node's blink to point to this new first node
			// first get the oldfirst_node from disk into memory
			read_flist_nd(oldfirst_node_offset, oldfirst_node, func_name);
			oldfirst_node->blink = new_node_offset;
			// write back the oldfirst_node to disk
			write_flist_nd(oldfirst_node_offset, oldfirst_node, func_name);
			// Finally, make this new first node point to the old first node
			      // f->flink = oldfirst_node;
			// read from disk to get the size of the new node's chunk (it should already be at this spot on disk)
			read_flist_nd(new_node_offset, newfirst_node, func_name);
			newfirst_node->flink = oldfirst_node_offset;
			// (newfirst_node gets finished & written to disk below)
	}
	else {   // if there are NO free-list nodes (then no old nodes need fields changed)
		// read from disk to get the size of the new node's chunk (it should already be at this spot on disk)
		read_flist_nd(new_node_offset, newfirst_node, func_name);
		newfirst_node->flink = 0; // blink gets set to 0 below. Flink = 0 since this will be only free-list nd
	}
	//////////////////////////////////////////////////
	// officially make newfirst_node the first node //
	free_head = new_node_offset;
	// write back the free_head
	fs.type_write(FREE_HEAD_PTR_POSITION, free_head, func_name);
	// finish filling out newfirst_node
	newfirst_node->blink = 0;  // equiv to NULL for this program
	// write back the newfirst_node to disk
	write_flist_nd(new_node_offset, newfirst_node, func_name);

	////////////////////////////////////////////////////////////////////////
	// Make sure to set global var to indicate that the list is not empty //
	free_list_empty = false;


	/*
	if( test_free ) { say "\nAt END of add_node(), free_list_begin(): <0x%lx>,  "\
			                  "f->flink: <0x%lx>,  f->blink: <0x%lx>\n", ULI free_list_begin(),
			                  ULI f->flink, ULI f->blink );
	}
	*/
}	/////////////////////// end function  add_node() //////////////////////	


// function: print_FList()
// purpose:  helper function for testing
void print_FList()
{
	char* func_name = "print_FList()";
	unsigned int offset = 0; 
	FList_node* f = new FList_node;
	int flist_size = 0; // to report the total size of free memory

	if( free_head != 0  ||  !free_list_empty ) {
		
		cout << "\nFree-list contains:  ";
		offset = free_head;

		read_flist_nd(offset, f, func_name);
		
		cout << "\n  f offset: <" << offset << ">, f->size: <" << f->size << ">";
		flist_size += f->size;

		// advance to next node while there is a next node
		while( f->flink != 0  )  {   
			offset = f->flink;  // make the next node the "current" node
			// read in the next node into f
			read_flist_nd(f->flink, f, func_name);
			cout << "\n  f offset: <" << offset << ">, f->size: <" << f->size << ">";
			flist_size += f->size;
		}
		cout << "\nEnd of Free-list\n";
		cout << "TOTAL FREE-LIST SIZE: " << flist_size << endl;
	}
	else {
		cout << "\n  Free List is empty." << endl;
	}
}  /////////////// end print_FList() ////////////////////////


// Function: print_carved_addr()
// Purpose:  Helper function for testing - prints all malloc's address  
void print_carved_addr()
{
	set <unsigned int>::iterator it;

	if(test_offsets.size() > 0)
 		cout << "\nHere's previous CARVED ADDRESSES that can be freed: ";
	else
		cout << "\nThere are currently no carved sections (only free-list node(s)).\n";

	//for( unsigned j = 0; j < test_offsets.size(); j++ ) {
	for( it = test_offsets.begin(); it != test_offsets.end(); it++ ) {
		cout << "\n     user offset: <" << *it << "> "; 
 	}
} //////////// end print_carved_addr() ///////////////////////


// Function: read_flist_nd()
// Purpose:  helper function calls fs.type_read() to read in all fields of an FList node at location "offset"
void read_flist_nd( unsigned int offset, FList_node* f, string func_name)
{
	fs.type_read( offset,    &(f->size),  func_name );
	fs.type_read_at_cur_pos( &(f->flink), func_name );
	fs.type_read_at_cur_pos( &(f->blink), func_name );
} //////// end read_flist_nd() /////////////////////

// Function: write_flist_nd()
// Purpose:  helper function calls fs.type_write() to write out all fields of an FList node at location "offset"
void write_flist_nd( unsigned int offset, FList_node* f, string func_name)
{
	fs.type_write( offset, f->size, func_name );
	fs.type_write_at_cur_pos( f->flink, func_name );
	fs.type_write_at_cur_pos( f->blink, func_name );
} //////// end read_flist_nd() /////////////////////


// function: carve_test_main()
// purpose:  tests out various functions depending on what user wants (command arguments)
// arguments: 
int carve_test_main()
{
	
	string go;
	unsigned int bytes;
	unsigned int offset;
	unsigned int to_free;
	

	cout << "\n\n-----------------------------------------------------------\n";
	cout << "\nWelcome to the test function for carve(), free(), and coelesce() for SimpleFS\n" << endl;
	//cout << "\nStarting # of free bytes is approx: " << FS_SIZE - 
	
	cout << "\nInitial state of disk:\n";
	cout << "\n  Total FS size: " << FS_SIZE << endl;

	print_FList();
	print_carved_addr();

	cout << "\n ----------------- \n";
	cout << "\nEnter # bytes to carve() (or -1 to quite):   ";
	cin >> bytes;
	
	while(bytes != -1)  {
		
		if(bytes > 0 ) {
			offset = carve(bytes);
			if(offset > 0) { 
				test_offsets.insert(offset);   
				cout << "\nAfter carving " << bytes << " bytes...";
				print_FList();
				print_carved_addr();
			}
			else {
				cout << "\nSorry dude, I couldn't find a free-list node big enough to satisfy your request.";
				cout << "\n(Coelescing not yet supported either)\n";
			}
		}

		cout << "\n\nEnter the offset of a chunk to be free'd (or 0 to skip this step):  ";
		cin >> to_free;
		if(to_free != 0 ) {
			my_free(to_free);
			cout << "\nAfter freeing offset " << to_free << "...";
			test_offsets.erase(to_free);
			print_FList();
			print_carved_addr();
		}

		cout << "\n\nEnter # bytes to carve(), or 0 to skip to free'ing (or -1 to quite):   ";
		cin >> bytes;
	}

	return 0;
} ///////// end carve_test_main() //////////////////